package com.lg.algorithm.leetcode.dt;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个整数数组 nums ，你可以对它进行一些操作。
 *
 * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，
 * 你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
 *
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
 *
 * 输入：nums = [3,4,2]
 * 输出：6
 * 解释：
 * 删除 4 获得 4 个点数，因此 3 也被删除。
 * 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
 *
 * 输入：nums = [2,2,3,3,3,4]
 * 输出：9
 * 解释：
 * 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
 * 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
 * 总共获得 9 个点数。
 *
 * 1 <= nums.length <= 2 * 104
 * 1 <= nums[i] <= 104
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-and-earn
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 *  把这个数组排序，然后按他们的差值是否大于1 切割成一个个小数组
 *
 *  然后就有 打家劫舍那个公式了，如果你选了一个，就不能选这一点两边的
 *
 *  如果说出现多次重复的，就不满足上面的思想，我们可以把这些重复的数合成一个数
 *      因为当我们选择一个数之后，必然要继续选择这个数，以保证我们能够最大
 */
public class DeleteAndEarn {

    public static void main(String[] args) {
//        int[] nums1 = {3, 4, 2};
//        int[] nums2 = {2,2,3,3,3,4};
        int[] nums3 = {3,1};
//        System.out.println(delAndEarn(nums1));
//        System.out.println(delAndEarn(nums2));
//        System.out.println(delAndEarn(nums3));

        System.out.println("------上边在多值重复的情况下有问题--------");
        System.out.println(rob(nums3));

    }

    /**
     * 重复的累加成一个新的大数，但是这个大数要在原来的位置，选这个大数，不选他原数两边的东西
     *
     * 构建一个数组，这个容量就是原数组中最大的值
     * 将值放入相对应的下标，那么这个数组就对应那些房子，上面的值就对应房子里的钱
     *
     */
    private static  int delAndEarn2(int[] nums) {
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int[] target = new int[max + 1];
        for (int num : nums) {
            target[num] += num;
        }

        return rob(target);
    }


    private static int rob(int[] nums) {
        //dp[i] = max(dp[i-2]+num[i],dp[i-1])
        int pre = 0;
        int curr = 0;
        for (int i = 0; i < nums.length; i++) {
            int next = Math.max(pre + nums[i], curr);
            pre = curr;
            curr = next;
        }
        return curr;

    }
    /**
     * 无法满足 多个数重复的问题
     * @param nums
     * @return
     */
    private static  int delAndEarn(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        Arrays.sort(nums);
        int sum = 0;
        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length-1; i++) {
            if ((nums[i + 1] - nums[i]) > 1) {
                temp.add(nums[i]);
                sum = sum + maxEarn(temp);
                temp = new ArrayList<>();
            } else {
                temp.add(nums[i]);
            }
        }
        if (temp.size()!=0 && (nums[nums.length - 1] - temp.get(temp.size() - 1)) > 1) {
            sum = sum + maxEarn(temp);
            sum = sum + nums[nums.length - 1];
        } else {
            temp.add(nums[nums.length - 1]);
            sum = sum + maxEarn(temp);
        }

        return sum;
    }

    private static int maxEarn(List<Integer> numsList) {
        //dp[i] = max(dp[i-2]+num[i],dp[i-1])
        Integer[] nums = new Integer[numsList.size()];
        numsList.toArray(nums);

        int pre = 0;
        int curr = 0;
        for (int i = 0; i < nums.length; i++) {
            int next = Math.max(pre + nums[i], curr);
            pre = curr;
            curr = next;
        }
        return curr;

    }





}
